package com.huangyi;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        //汉诺塔
        class Solution {
            public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
                move(A, B, C, A.size()); // 把 A 的 n 个盘借助 B 移到 C（原地修改）
            }

            private void move(List<Integer> from, List<Integer> aux, List<Integer> to, int n) {
                if (n <= 0) return;               // 终止：没有盘子可搬
                move(from, to, aux, n - 1);       // 1) 先把 n-1 从 from -> aux
                moveTop(from, to);                // 2) 再把最大盘 from -> to
                move(aux, from, to, n - 1);       // 3) 最后把 n-1 从 aux -> to
            }

            // 栈顶移动：List 的最后一个元素为“顶盘”
            private void moveTop(List<Integer> from, List<Integer> to) {
                to.add(from.remove(from.size() - 1));
            }
        }

        //两两交换链表中的节点
        /**
         * Definition for singly-linked list.
         * public class ListNode {
         *     int val;
         *     ListNode next;
         *     ListNode() {}
         *     ListNode(int val) { this.val = val; }
         *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
         * }
         */
        class Solution2 {
            public ListNode swapPairs(ListNode head) {
                return swap(head);
            }

            private ListNode swap(ListNode head){
                // 基线：空链或单节点，原样返回（同时兜住奇偶两种结尾）
                if (head == null || head.next == null) return head;

                // 先处理后半段（从第 3 个开始），拿到已交换好的新头
                ListNode tmp = swap(head.next.next);

                // 当前一对：a=head, b=head.next
                ListNode cur = head.next;     // b
                head.next.next = head;        // b -> a（翻转当前一对）
                head.next = tmp;              // a -> 后半段新头

                return cur;                   // 返回当前段的新头（b）
            }
        }
    }
}